# -*- coding: utf-8 -*-

from mathematics import *
from log import *

#point
class Point:
    
    def __init__(self, x, y):
	try:
	    self.x = float(x)
	    self.y = float(y)
	except ValueError, e:
	    self.x = 0
	    self.y = 0

    def __str__(self):
	return "(%g, %g)" % (self.x, self.y)

    def x(self):
	return self.x

    def y(self):
	return self.y

    def __eq__(self, other):
	return self.x == other.x and self.y == other.y

#line
class Line:

    def __init__(self, p0, p1):
	self.p0 = p0
	self.p1 = p1

    def __str__(self):
	return "%s-%s" % (self.p0, self.p1)

    def p0(self):
	return self.p0

    def p1(self):
	return self.p1

    def f(self, x):
	y = [0.0]*len(x)
	for i in range(len(x)):
	    if not self.contain(x[i]):
		continue
	    if self.p0.y == self.p1.y:
		y[i] = self.p0.y
	    else: # (x-x1)/(x2-x1) = (y-y1)/(y2-y1)
		y[i] = self.p0.y + (self.p1.y - self.p0.y)*(x[i] - self.p0.x)/(self.p1.x - self.p0.x)
	return y

    def fx(self, x):
	x = [float(x)]
	return self.f(x)[0]

    def contain (self, x):
	if self.p0.x <= x <= self.p1.x:
	    return True
	return False
    
    def farea(self, x, *args):
	y = 0
	if not self.contain(x):
	    return y
	if self.p0.y == self.p1.y:
	    y = self.p0.y
	else: # (x-x1)/(x2-x1) = (y-y1)/(y2-y1)
	    y = self.p0.y + (self.p1.y - self.p0.y)*(x - self.p0.x)/(self.p1.x - self.p0.x)
	    
	if len(args):
	    return min(y, args[0])
	return y

    def moment(self, x, *args):
	y = 0
	if len(args):
	    y = self.farea(x, args[0])
	else:
	    y = self.farea(x)
	return x * y

    # функция вычисялет f(x) и ищет х по заданной точке y
    def y2x(self, x, y):
	l = len(x)
	f = self.f(x)
	# точное значение
	for i in range(l):
	    if f[i] == y:
		#print "%s == %g" % (self.__str__(), x[i])
		return x[i]
	# приближенное значение
	for i in range(1,l-1):
	    if self.p0.y < self.p1.y: #grow
		if f[i-1] <= y <= f[i+1]:
		    #print "%s <> %g" % (self.__str__(), x[i])
		    return x[i]
	    elif self.p0.y > self.p1.y: #fall
		if f[i+1] <= y <= f[i-1]:
		    #print "%s <> %g" % (self.__str__(), x[i])
		    return x[i]
	return None

# peak
class Peak:

    def __init__(self, lines):
	self.lines = []
	try:
	    for line in lines:
		self.lines.append(line)
	except TypeError, e:
	    pass

    # для with
    def __enter__(self):
	return self

    def __exit__(self, type, value, traceback):
	pass

    def __str__(self):
	s = ""
	for line in self.lines:
	    if s:
		s += " & "
	    s += "%s" % line
	return s

    def f(self, x):
	y = [0.0]*len(x)
	for line in self.lines:
	    z = line.f(x)
	    for i in range(len(z)):
		if z[i]:
		    y[i] = z[i]
	return y

    def fx(self, x):
	y = 0
	for line in self.lines:
	    y = max(y, line.fx(x));
	return y

    def contain(self, x):
	for line in self.lines:
	    if line.contain(x):
		return True
	return False
	
    def _farea(self, x, *args):
	y = 0
	if not self.contain(x):
	    return y
	for line in self.lines:
	    z = line.farea(x, *args)
	    y += z
	    #print "line.farea(%g) %s=%g" % (x, line, z)
	return y

    def farea(self):
	return self._farea

    def _moment(self, x, *args):
	y = 0
	if not self.contain(x):
	    return y
	for line in self.lines:
	    z = 0
	    if len(args):
		z = line.moment(x, self.fx(args[0]))
	    else:
		z = line.moment(x)
	    y += z
	    #print "line.moment(%g) %s=%g" % (x, line, z)
	return y

    def moment(self):
	return self._moment

    def gravity(self, *args):
	xpoints = self.points()['x']
	a = xpoints[0]
	b = xpoints[-1]
	farea = Math.integral(self._farea, a, b, *args)
	moment = Math.integral(self._moment, a, b, *args)
	if farea == 0:
	    return (a + b) / 2
	return moment/farea

    # функция вычисляет точки пересечения прямой f(x)=y и графика функции
    def y2x(self, x, y):
	r = []
	for line in self.lines:
	    z = line.y2x(x, y)
	    if not z == None:
		r.append(z)
	return r

    # возвращает массивы точек x,y
    def points(self):
	o = { 'x':[], 'y':[] }
	if not len(self.lines):
	    return o
	for line in self.lines:
	    o['x'].append(line.p0.x)
	    o['y'].append(line.p0.y)
	o['x'].append(self.lines[-1].p1.x)
	o['y'].append(self.lines[-1].p1.y)
	return o

    # Для операций сравнения, в частности сортировки
    def __eq__(self, other):
	return self.lines[0].p0.x == other.lines[0].p0.x and self.lines[-1].p1.x == other.lines[-1].p1.x

    def __ne__(self, other):
	return not self.lines[0].p0.x == other.lines[0].p0.x and self.lines[-1].p1.x == other.lines[-1].p1.x

    def __le__(self, other):
	return self.lines[0].p0.x <= other.lines[0].p0.x and self.lines[-1].p1.x <= other.lines[-1].p1.x

    def __lt__(self, other):
	return (self.lines[0].p0.x < other.lines[0].p0.x and self.lines[-1].p1.x <= other.lines[-1].p1.x) or (self.lines[0].p0.x <= other.lines[0].p0.x and self.lines[-1].p1.x < other.lines[-1].p1.x)

    def __ge__(self, other):
	return self.lines[0].p0.x >= other.lines[0].p0.x and self.lines[-1].p1.x >= other.lines[-1].p1.x

    def __gt__(self, other):
	return (self.lines[0].p0.x > other.lines[0].p0.x and self.lines[-1].p1.x >= other.lines[-1].p1.x) or (self.lines[0].p0.x >= other.lines[0].p0.x and self.lines[-1].p1.x > other.lines[-1].p1.x)

#var
class Var:

    def __init__(self, name, peaks):
	self.name = name
	self.peaks = []
	try:
	    for peak in peaks:
		self.peaks.append(peak)
	except TypeError, e:
	    pass

    def __str__(self):
	s = ""
	for peak in self.peaks:
	    if s:
		s += "\n"
	    s += "\t%s" % peak
	return (self.name + ":\n" + s)

    def f(self, x):
	funcs = []
	for peak in self.peaks:
	    y = peak.f(x)
	    funcs.append(y)
	return funcs

    #вычисление "зуба" (пересечение и отсечение "шапки" по альфа-уровням каждого из забов, в который попадает точка) для точки xi
    def fx(self, x, xi):
	y = [0.0] * len(x)
	# массив f(x) "зубов" ЛП
	yi = []
	# массив пороговых значений y 
	fx = []
	for peak in self.peaks:
	    if peak.contain(xi):
		# f(x)
		func = peak.f(x)
		yi.append(func)
		# пороговое значение y
		f = peak.fx(xi)
		fx.append(f)
	for i in range(len(x)):
	    for k in range(len(yi)):
		y[i] = max(y[i], min(yi[k][i], fx[k]))
	return y


def points2peak(x, y):
    lines = []
    lx = len(x)
    ly = len(y)
    
    if not lx or not ly or lx != ly:
	return None

    for i in range(lx-1):
	if y[i] == 0 and y[i+1] == 0: #skip lines y=0
	    continue
	p0 = Point(x[i], y[i])
	p1 = Point(x[i+1], y[i+1])
	line = Line(p0, p1)
	lines.append(line)
    return Peak(lines)

#!!!TODO: refact
#friend funcs
def lines2peaks (lines, debug = False):

    if not lines:
	return []

# build uniq long sequences
    peaks = []
    logger = Logger(debug)

    for line in lines:
	logger.debug("line %s" % line)
	put = 0
	for peak in peaks:
	    for peakline in peak:
		logger.debug("peakline %s" % peakline)
		if peakline.p0 == line.p1 or peakline.p1 == line.p0:
		    logger.debug("\tappend")
		    put = 1
		    peak.append(line)
		    break
	    if put:
		break
	if put:
	    continue
	logger.debug("\tappend new")
	peaks.append([line,])

# split by y == 0
    logger.debug("split by y==0")
    peaks_new = []
    
    for peak in peaks:
	idx = lidx = 0
	cnt = len(peak)
	for peakline in peak:
	    if idx + 1 < cnt and peakline.p1.y == 0:
		logger.debug("\tsplit by %s [%d:%d]" % (peakline.p1, lidx, idx))
		peaks_new.append(peak[lidx:idx+1])
		lidx = idx + 1
	    idx += 1
	peaks_new.append(peak[lidx:cnt])
	logger.debug("\tsplit by %s [%d:%d]" % (peakline.p1, lidx, cnt-1))

    peaks = peaks_new

# found intersection
    logger.debug("intersections")
    intersect = []
    intersect_new = []
    for peak in peaks:
	if peak[0].p0.y == 0 or peak[-1].p1.y == 0:
	    continue
	intersect.append(peak)
	logger.debug("\t%s" % peak)

    for i in intersect:
	cnt = len(i)
	p_head = i[0].p0
	p_tail = i[-1].p1
	found = False
	for peak in peaks:
	    if i == peak:
		continue
	    peaklen = len(peak)
	    p = 0
	    l_idx = r_idx = 0
	    while p < peaklen:
		peakline = peak[p]
		if p_head.y and p_head == peakline.p1:
		    l_idx = 0
		    r_idx = p + 1
		    logger.debug('p1=%s [%d] %d-%d' % (peakline.p1, p, l_idx, r_idx))
		    found = True
		    break
		if p_tail.y and p_tail == peakline.p0:
		    l_idx = p
		    r_idx = peaklen
		    logger.debug('p0=%s [%d] %d-%d' % (peakline.p0, p, l_idx, r_idx))
		    found = True
		    break
		p += 1
	    if found:
		intersect_new.append(i + peak[l_idx:r_idx])
		break
	pass

    for i in intersect:
	logger.debug("remove %s" % i)
	peaks.remove(i)
	
    for i in intersect_new:
	logger.debug("\t%s" % i)
	peaks.append(i)

# result
    ret = []
    for peak in peaks:
	ret.append(Peak(peak))

    return ret

